import java.text.DecimalFormat;
import java.text.NumberFormat;

public class Apl {
	public static void main(String[] args) {
		new Apl();
	}

	public static int TIMES_TO_RUN = 5;
	public int[] amountArray = { 10000, 100000, 1000000 };
	
	public Apl() {
		long startTime = System.currentTimeMillis();
		
		opdracht1();
		System.out.println("\n\n");
		opdracht2();
		System.out.println("\n\n");
		
		int[] minimumValues = { 10, 100, 1000, 1000, 10000 };
		for(int minimumValue : minimumValues) {
			opdracht3(minimumValue);
		}

		long endTime = System.currentTimeMillis();
		
		System.out.println("#####################################################");
		System.out.println(">> Program Execution time is "+ formatter.format((endTime - startTime) / 1000d) +" seconds.");
		System.out.println("#####################################################");
	}
	
	NumberFormat formatter = new DecimalFormat("#0.00000");
	
	public void opdracht1() {
		System.out.println("Opdracht 1, insertion sort in een enkele thread.");
		for (int i = 0; i < amountArray.length; i++) {
			System.out.println("Insertion sort for '"+ amountArray[i] +"' random numbers.");

			long totaltime = 0;
			for(int j = 0; j < TIMES_TO_RUN; j++) {
				int[] numbers = generateArray(amountArray[i]);
	
				long startTime = System.currentTimeMillis();
				insertionSort(numbers);
	
				long endTime = System.currentTimeMillis();
				
				totaltime += (endTime - startTime);
				System.out.println("Execution time is "+ formatter.format((endTime - startTime) / 1000d) +" seconds.");
				System.err.println("isSorted: ("+ amountArray[i] +" == "+ numbers.length +") - "+ (isSorted(numbers) && amountArray[i] == numbers.length));
			}

			System.out.println(">>> Avarage time is "+ formatter.format((totaltime / TIMES_TO_RUN) / 1000d) +" seconds.");
			System.out.println("#######################################");
		}
	}

	public void opdracht2() {
		System.out.println("Opdracht 2, insertion sort met twee threads.");
		for (int i = 0; i < amountArray.length; i++) {
			System.out.println("Insertion sort for '"+ amountArray[i] +"' random numbers.");
			
			long totaltime = 0;
			for(int j = 0; j < TIMES_TO_RUN; j++) {
				int[] numbers = generateArray(amountArray[i]);
	
				long startTime = System.currentTimeMillis();
	
				// Array opdelen in 2 stukken
				int half = (int)(numbers.length / 2); // Om er zeker van te zijn dat er naar beneden word afgerond
				int[] firstHalf = new int[half];
				int[] secondHalf = new int[numbers.length - half];
				
				System.arraycopy(numbers, 0, firstHalf, 0, firstHalf.length);
				System.arraycopy(numbers, firstHalf.length, secondHalf, 0, secondHalf.length);
	
				// 2 threads starten en elk de helft van de getallen meegeven
				Thread threadFirstHalf = new Opdracht2Thread(firstHalf);
				Thread threadSecondHalf = new Opdracht2Thread(secondHalf);
				threadFirstHalf.start();
				threadSecondHalf.start();
	
				try {
					threadFirstHalf.join();
					threadSecondHalf.join();
				} catch (InterruptedException e) {
					System.out.println(e.getMessage());
				}
				numbers = mergeSort(firstHalf, secondHalf);
				
				long endTime = System.currentTimeMillis();
				totaltime += (endTime - startTime);
				System.out.println("Execution time is "+ formatter.format((endTime - startTime) / 1000d) +" seconds.");
				System.err.println("isSorted: ("+ amountArray[i] +" == "+ numbers.length +") - "+ (isSorted(numbers) && amountArray[i] == numbers.length));
			}
			
			System.out.println(">>> Avarage time is "+ formatter.format((totaltime / TIMES_TO_RUN) / 1000d) +" seconds.");
			System.out.println("#######################################");
		}
	}

	public void opdracht3(int minimumValue) {
		System.out.println("Opdracht 3, insertion sort met meerdere threads.");
		for (int i = 0; i < amountArray.length; i++) {
			System.out.println("Insertion sort for '"+ amountArray[i] +"' random numbers.");
			System.out.println("Minimum value: "+ minimumValue);
			
			long totaltime = 0;
			for(int j = 0; j < TIMES_TO_RUN; j++) {
				int[] numbers = generateArray(amountArray[i]);
	
				long startTime = System.currentTimeMillis();
				
				Opdracht3Thread thread = new Opdracht3Thread(numbers, minimumValue);
				thread.start();
				
				try {
					thread.join();
				} catch (InterruptedException e) {
					System.out.println(e.getMessage());
				}
				// stop the time
				long endTime = System.currentTimeMillis();
				totaltime += (endTime - startTime);
				System.out.println("Execution time is "+ formatter.format((endTime - startTime) / 1000d) +" seconds.");
				System.err.println("isSorted: ("+ amountArray[i] +" == "+ numbers.length +") - "+ (isSorted(thread.getNumbers()) && amountArray[i] == numbers.length));
			}

			System.out.println(">>> Avarage time is "+ formatter.format((totaltime / TIMES_TO_RUN) / 1000d) +" seconds.");
			System.out.println("#######################################");
		}		
	}

	public static int[] generateArray(int totalNumbers) {
		int[] numbers = new int[totalNumbers];
		for (int i = 0; i < totalNumbers; i++) {
			numbers[i] = (int) Math.floor(Math.random() * 1000);
		}
		return numbers;
	}

	/**
	 * Method to print an array, to see if it is sorted.
	 */
	public static void printArray(int[] array) {
		String output = "";
		for (int i = 0; i < array.length; i++) {
			output += array[i] + ", ";
		}
		System.out.println(output);
	}

	public static boolean isSorted(int[] array) {
		boolean sorted = true;
		for (int i = 1; i < array.length; i++) {
			if (array[i - 1] > array[i]) {
				sorted = false;
				break;
			}
		}

		return sorted;
	}

	/**
	 * Insertion sort method based on algorithm found on the internet.
	 */
	public void insertionSort(int[] input) {
		int index;
		int newValue;

		for (int i = 1; i < input.length; i++) {
			newValue = input[i];
			index = i;
			while (index > 0 && input[index - 1] > newValue) {
				input[index] = input[index - 1];
				index--;
			}
			input[index] = newValue;
		}
	}

	public int[] mergeSort(int left[], int right[]){
		int[] result = new int[left.length + right.length];
		int leftPosition = 0, rightPosition = 0, resultPosition = 0;
		
		while(leftPosition < left.length && rightPosition < right.length){
			if(left[leftPosition] < right[rightPosition]){
				result[resultPosition++] = left[leftPosition++];
			} else {
				result[resultPosition++] = right[rightPosition++];
			}
		}
		
		while(leftPosition < left.length){
			result[resultPosition++] = left[leftPosition++];
		}
		
		while(rightPosition < right.length){
			result[resultPosition++] = right[rightPosition++];
		}
		
		return result;
	}
	
	public class Opdracht2Thread extends Thread {

		int[] numbers;

		public Opdracht2Thread(int[] numbers) {
			this.numbers = numbers;
		}

		@Override
		public void run() {
			insertionSort(numbers);
		}
	}

	public class Opdracht3Thread extends Thread {
		public int[] numbers;
		public int minimumValue;

		public Opdracht3Thread(int[] numbers, int minimumValue) {
			this.numbers = numbers;
			this.minimumValue = minimumValue;
		}

		@Override
		public void run() {
			if(numbers.length > minimumValue) {
				int half = (int)(numbers.length / 2); // Om er zeker van te zijn dat er naar beneden word afgerond
				int[] firstHalf = new int[half];
				int[] secondHalf = new int[numbers.length - half];
				
				System.arraycopy(numbers, 0, firstHalf, 0, firstHalf.length);
				System.arraycopy(numbers, firstHalf.length, secondHalf, 0, secondHalf.length);
	
				// 2 threads starten en elk de helft van de getallen meegeven
				Opdracht3Thread threadFirstHalf = new Opdracht3Thread(firstHalf, minimumValue);
				Opdracht3Thread threadSecondHalf = new Opdracht3Thread(secondHalf, minimumValue);
				threadFirstHalf.start();
				threadSecondHalf.start();
	
				try {
					threadFirstHalf.join();
					threadSecondHalf.join();
				} catch (InterruptedException e) {
					System.out.println(e.getMessage());
				}
				
				numbers = mergeSort(threadFirstHalf.getNumbers(), threadSecondHalf.getNumbers());
			} else {
				insertionSort(numbers);
			}
		}
		
		public int[] getNumbers() {
			return numbers;
		}
	}
}
